
package main.old.new_2023.last.month_9;


import java.util.*;

/**
 * @Description: todo 1462. 课程表 IV
 * 你总共需要上 numCourses 门课，课程编号依次为 0 到 numCourses-1 。
 * 你会得到一个数组 prerequisite ，其中 prerequisites[i] = [ai, bi] 表示如果你想选 bi 课程，你 必须 先选 ai 课程。
 * 有的课会有直接的先修课程，比如如果想上课程 1 ，你必须先上课程 0 ，那么会以 [0,1] 数对的形式给出先修课程数对。
 * 先决条件也可以是 间接 的。如果课程 a 是课程 b 的先决条件，课程 b 是课程 c 的先决条件，那么课程 a 就是课程 c 的先决条件。
 * 你也得到一个数组 queries ，其中 queries[j] = [uj, vj]。对于第 j 个查询，您应该回答课程 uj 是否是课程 vj 的先决条件。
 * 返回一个布尔数组 answer ，其中 answer[j] 是第 j 个查询的答案。
 * todo 2596. 检查骑士巡视方案
 * 骑士在一张 n x n 的棋盘上巡视。在有效的巡视方案中，骑士会从棋盘的 左上角 出发，并且访问棋盘上的每个格子 恰好一次 。
 * 给你一个 n x n 的整数矩阵 grid ，由范围 [0, n * n - 1] 内的不同整数组成，
 * 其中 grid[row][col] 表示单元格 (row, col) 是骑士访问的第 grid[row][col] 个单元格。骑士的行动是从下标 0 开始的。
 * 如果 grid 表示了骑士的有效巡视方案，返回 true；否则返回 false。
 * 注意，骑士行动时可以垂直移动两个格子且水平移动一个格子，或水平移动两个格子且垂直移动一个格子。下图展示了骑士从某个格子出发可能的八种行动路线。
 *
 * @Author: Take-off
 * @Date: 1:00 PM 2023/6/
 * @Param:
 * @return:
 **/
public class Solution0913 {

    //检查骑士巡视方案
    public boolean checkValidGrid(int[][] grid) {
        if (grid[0][0] != 0) {
            return false;
        }
        int n = grid.length;
        int[][] indices = new int[n * n][2];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                indices[grid[i][j]][0] = i;
                indices[grid[i][j]][1] = j;
            }
        }
        for (int i = 1; i < n * n; i++) {
            int dx = Math.abs(indices[i][0] - indices[i - 1][0]);
            int dy = Math.abs(indices[i][1] - indices[i - 1][1]);
            if (dx * dy != 2) {
                return false;
            }
        }
        return true;
    }

    //课程表 IV - 构成邻接表，
    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        List<Boolean> result = new ArrayList<>();
        //保存课程相互关联的关系，下标为课程记号，值为需要先完成的课程
        List<List<Integer>> courseRelation = new ArrayList<>();
        for (int i = 0;i<numCourses;i++){
            courseRelation.add(new ArrayList<>());
        }
        for (int[] coures:prerequisites){
            //先读了 coures[1] 才能 读 coures[0]
            List<Integer> couseTemp = courseRelation.get(coures[1]);
            couseTemp.add(coures[0]);
            courseRelation.set(coures[1],couseTemp);
        }
        for (int[] query:queries){
            //检查先决条件
            result.add(check(query,courseRelation));
        }
        return result;
    }
    private boolean check(int[] query,List<List<Integer>> courseRelation){
        boolean flag = false;
        int target = query[0];
        List<Integer> courses = courseRelation.get(query[1]);
        if (courses.size() >0){
            if (courses.contains(target)){
                return true;
            }
            Set<Integer> courseSet = new HashSet<>(courses);
            Queue<Integer> queue = new LinkedList<>(courses);
            while (!queue.isEmpty()){
                for (Integer temp:courseRelation.get(queue.poll())){
                    if (temp == target){
                        return true;
                    }
                    if (!courseSet.contains(temp)){
                        courseSet.add(temp);
                        queue.add(temp);
                    }
                }
            }
        }
        return flag;
    }

    public static void main(String[] args) {
        int[][] ints ={{0,3,6},{5,8,1},{2,7,4}};
        Solution0913 test = new Solution0913();
        test.checkValidGrid(ints);
    }

}
